#include "../tools.h"

class Solution {
public:
    int maxpath = INT32_MIN;
    int track(TreeNode* tree){
        if(tree == nullptr) return 0;

        int lsum = track(tree->left);
        int rsum = track(tree->right);
        
        if(lsum <= 0 && rsum <= 0){
            maxpath = max(tree->val, maxpath);
            cout << maxpath << endl;
            return tree->val;
        }

        int cursum = tree->val;
        if(lsum > 0) cursum += lsum;
        if(rsum > 0) cursum += rsum;
        maxpath = max(cursum, maxpath); // 截止
        // 向上传播
        return max(lsum, rsum) + tree->val;
    }

    int maxPathSum(TreeNode* root) {
        if(root == nullptr) return 0;

        int res = track(root);
        return max(res, maxpath);

    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    // vector<int> root = {3,9,20,-1,-1,15,7};
    // vector<int> root = {1,2,2,3,3,-1,-1,4,4};
    vector<int> nums = {-2,-1,9,-6,3,-1,-1,-1,-2};
    TreeNode* tree = create_tree(nums);
    show(tree);

    auto res = sol.maxPathSum(tree);

    cout << res;


    return 0;
}
